\chapter{Fundamentals}
This chapter gives some basic definitions of the terms which are frequently used in the report.
\newline
\begin{description}[font=\normalfont\itshape\textbullet\space]
	\item[Polynomial time Algorithm:] An algorithm running on an input of length n, is said to be polynomial-time if its running time f(n) = O($n^c$), where c is a positive constant. We write y = A(x) to denote the output of an algorithm A on input x.

	\item[Probabilistic Polynomial Time Algorithm:]An algorithm that is randomized (has a source of randomness) and runs in polynomial amount of time is referred to as a probabilistic polynomial time algorithm.  We write y =A(x,r) to denote the output of an algorithm A on input x, when r were the internal coin tosses made by A. (r is a polynomial in k).

	\item[Negligible function$\label{def_2_3}$:] A function $\varepsilon(k)$ is negligible in cryptography, if for every polynomial p(.), an integer N exists such that for all integers k $>$ N it holds that $\varepsilon(k) < \frac{1}{p(k)} $. $\cite{katz2007introduction}$
\newline
Intuitively this means that a negligible functions approaches zero faster than the inverse of a polynomial. In cryptography a system is said to be secure if an adversary has only negligible advantage in guessing key parameters.

	\item[Probabilistic Polynomial adversary:] An antagonist  having only probabilistic polynomial computing power.

	\item[Random Oracle Model:] It captures the concept of an ideal hash function. It says if a hash function is ideal then the hash of a given value can only be computed by actually computing it, i.e. even if many previous values are known.

	\item[Cryptographic One-way hash functions:] A cryptographic hash function is a transformation (H: M $\longrightarrow$ Y) that takes an input (or 'message') and returns a fixed-size alphanumeric string, which is called the hash value. It follows the random oracle model and has these properties: 
\newline
a) Preimage Resistance: Given a hash y, it is hard to find the message m such that y=hash(m).
\newline
b) Collision Resistance: It is hard to find two different messages m and m1 such that hash(m) = hash(m1).
\newline
c) 2nd Preimage resistance: Given message m, it is difficult to find message m1 which hashes to the same value as the message m, i.e. hash(m) = hash(m1).

	\item[Group:] A group is a set of elements bound by an operation such that two elements of a group under that operation produce the third element. It is mandatory for a group to satisfy four group axioms namely closure, associative, identity and invertibility. Groups will be used in BGLS scheme.
Set of integers under Addition operation is quite a famous example of an additive group. It satisfies all four properties:
	\begin{enumerate}
		\item 2+2 = 4 (Closure Property)
		\item 2+(3+4) = (2+3)+4 (Associative Property)
		\item '0' is the additive identity and is present in the set of integers
		\item Additive Inverse of every integer is present within the set of integers as +1 and -1 etc.
	\end{enumerate}
Multiplicative group will be a group defined under the multiplication operation. Set of rational numbers is an example of such a group.
	\item[Group of Prime Order P:] Order of a group is defined as the cardinality of the group or the smallest positive integer 'm' such that an element 'a' raised to power 'm' is equal to identity element 'e' of that group i.e. a$^m$=e. a$^m$ means 'a' is operated with 'a' under the group operation 'm' times. Group of prime order P means that every element in the group has a prime order p.
\end{description}